package com.acwing.partition3;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/2/13 18:53
 */
public class AC245你能回答这些问题吗 {

    private static final int N = 500010;
    private static int[] a = new int[N];
    private static Node[] tr = new Node[N << 2];

    private static int n = 0, m = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        ss = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) a[i + 1] = Integer.parseInt(ss[i]);
        build(1, 1, n);
        for (int i = 0; i < m; i++) {
            ss = reader.readLine().split(" ");
            int a = Integer.parseInt(ss[0]), b = Integer.parseInt(ss[1]), c = Integer.parseInt(ss[2]);
            if (a == 1) {
                if (b > c) {
                    int t = b;
                    b = c;
                    c = t;
                }
                Node res = query(1, b, c);
                writer.write(res.ms + "\n");
            } else {
                modify(1, b, c);
            }
        }
        writer.flush();
    }

    private static Node query(int u, int l, int r) {
        if (l <= tr[u].l && r >= tr[u].r) return tr[u];
        else {
            int mid = tr[u].l + tr[u].r >> 1;
            //如果整个区间都在左边，就查询左边；整个区间都在右边就查询右边；如果需要横跨区间，另外特殊处理
            if (r <= mid) return query(u << 1, l, r);
            if (l > mid) return query(u << 1 | 1, l, r);
            //需要根据查询的子节点信息构建一个横跨的中间节点
            Node left = query(u << 1, l, r), right = query(u << 1 | 1, l, r);
            Node res = new Node(-1, -1);
            pushUp(res, left, right);
            return res;
        }
    }

    private static void modify(int u, int x, int v) {
        if (tr[u].l == x && tr[u].r == x) tr[u].sum = tr[u].mls = tr[u].mrs = tr[u].ms = v;
        else {
            int mid = tr[u].l + tr[u].r >> 1;
            if (x <= mid) modify(u << 1, x, v);
            else modify(u << 1 | 1, x, v);
            pushUp(tr[u], tr[u << 1], tr[u << 1 | 1]);
        }
    }

    private static void pushUp(Node u, Node l, Node r) {
        u.sum = l.sum + r.sum;
        u.mls = Math.max(l.mls, l.sum + r.mls);
        u.mrs = Math.max(r.mrs, l.mrs + r.sum);
        u.ms = Math.max(Math.max(l.ms, r.ms), l.mrs + r.mls);
    }

    private static void build(int u, int l, int r) {
        if (l == r) tr[u] = new Node(l, r, a[l], a[l], a[l], a[l]);
        else {
            tr[u] = new Node(l, r);
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushUp(tr[u], tr[u << 1], tr[u << 1 | 1]);
        }
    }

    private static class Node {
        private int l, r;
        //分别维护一个区间和、最大前缀和、最大后缀和、最大连续子段和
        private int sum, mls, mrs, ms;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
        }

        public Node(int l, int r, int sum, int mls, int mrs, int ms) {
            this.l = l;
            this.r = r;
            this.sum = sum;
            this.mls = mls;
            this.mrs = mrs;
            this.ms = ms;
        }
    }
}
